//给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充
//。
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O",
//"X","X"]]
//输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
//解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都
//会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
// 
//
// 示例 2： 
//
// 
//输入：board = [["X"]]
//输出：[["X"]]
// 
//
// 
//
// 提示： 
//
// 
// m == board.length 
// n == board[i].length 
// 1 <= m, n <= 200 
// board[i][j] 为 'X' 或 'O' 
// 
// 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 👍 888 👎 0


package com.cjl.leetcode.editor.cn;

/**
 * [P130]_被围绕的区域
 *
 * @author cjl
 * @date 2022-10-30 18:38:42
 */
public class P130_SurroundedRegions {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P130_SurroundedRegions().new Solution();
        char[][] board = {{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};
        solution.solve(board);
    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 从边框上找数字0，扩展标记，已标记位置无需标记，未标记位置全部填充X
         *
         * @param board
         */
        public void solve(char[][] board) {
            //标记不可置为
            int height = board.length;
            int width = board[0].length;
            int[][] flag = new int[height][width];
            for (int i = 0; i < height; i++) {
                solve(board, flag, i, 0);
                solve(board, flag, i, width - 1);
            }
            for (int i = 0; i < width; i++) {
                solve(board, flag, 0, i);
                solve(board, flag, height-1, i);
            }
            for(int i = 0 ; i < height ; i++){
                for(int j = 0; j < width; j++){
                    if(board[i][j] == 'O' && flag[i][j] != -1){
                        board[i][j] = 'X';
                    }
                }
            }
        }

        /**
         * @param board
         * @param flag
         * @param i
         * @param j
         * @return 是否需要循环遍历
         */
        public boolean solve(char[][] board, int[][] flag, int i, int j) {
            if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length-1) {
                return false;
            }
            //已处理节点
            if(flag[i][j] == -1){
                return false;
            }
            //X节点，无需处理
            if(board[i][j] == 'X'){
                flag[i][j] = -1;
                return false;
            }else{
                flag[i][j] = -1;
            }
            boolean b1 = solve(board, flag, i+1, j);
            boolean b2 = solve(board, flag, i-1, j);
            boolean b3 = solve(board, flag, i , j+1);
            boolean b4 = solve(board, flag, i , j -1);
            return b1 || b2 || b3 || b4;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}